//
// Created by pzw on 24-3-1.
//

#include "TreeSet.h"

/*构造函数*/
template<typename T>
TreeSet<T>::TreeSet() = default;

template<typename T>
TreeSet<T>::TreeSet(const std::set<T> &s) : treeSet(s) {}

template<typename T>
TreeSet<T>::TreeSet(TreeSetComparator<int> comparator) : comparator(comparator) {}

/*添加和删除元素*/
template<typename T>
bool TreeSet<T>::add(const T &e) {
    return treeSet.insert(e).second;
}

template<typename T>
bool TreeSet<T>::addAll(const std::set<T> &s) {
    bool changed = false;
    for (const auto &elem: s) {
        changed |= add(elem);
    }
    return changed;
}

template<typename T>
bool TreeSet<T>::remove(const T &e) {
    return treeSet.erase(e) > 0;
}

template<typename T>
void TreeSet<T>::clear() {
    treeSet.clear();
}

/*访问元素*/
template<typename T>
T TreeSet<T>::first() {
    if (treeSet.empty()) {
        return T(); // 返回默认值，可以根据具体情况修改
    }
    return *treeSet.begin();
}

template<typename T>
T TreeSet<T>::last() {
    if (treeSet.empty()) {
        return T(); // 返回默认值，可以根据具体情况修改
    }
    return *treeSet.rbegin();
}

template<typename T>
T TreeSet<T>::lower(T e) {
    auto it = treeSet.lower_bound(e);
    if (it == treeSet.begin()) {
        return T(); // 返回默认值，可以根据具体情况修改
    }
    return *(--it);
}

template<typename T>
T TreeSet<T>::higher(T e) {
    auto it = treeSet.upper_bound(e);
    if (it == treeSet.end()) {
        return T(); // 返回默认值，可以根据具体情况修改
    }
    return *it;
}

template<typename T>
T TreeSet<T>::floor(T e) {
    auto it = treeSet.lower_bound(e);
    if (it == treeSet.end() || *it > e) {
        if (it == treeSet.begin()) {
            return T(); // 返回默认值，可以根据具体情况修改
        }
        return *(--it);
    }
    return *it;
}

template<typename T>
T TreeSet<T>::ceiling(T e) {
    auto it = treeSet.lower_bound(e);
    if (it == treeSet.end()) {
        return T(); // 返回默认值，可以根据具体情况修改
    }
    return *it;
}

template<typename T>
T TreeSet<T>::pollFirst() {
    if (treeSet.empty()) {
        return T(); // 返回默认值，可以根据具体情况修改
    }
    T firstElem = *treeSet.begin();
    treeSet.erase(treeSet.begin());
    return firstElem;
}

template<typename T>
T TreeSet<T>::pollLast() {
    if (treeSet.empty()) {
        return T(); // 返回默认值，可以根据具体情况修改
    }
    T lastElem = *treeSet.rbegin();
    treeSet.erase(--treeSet.end());
    return lastElem;
}

/*集合操作*/
template<typename T>
int TreeSet<T>::size() {
    return treeSet.size();
}

template<typename T>
bool TreeSet<T>::isEmpty() {
    return treeSet.empty();
}

template<typename T>
bool TreeSet<T>::contains(const T &e) {
    return treeSet.find(e) != treeSet.end();
}

template<typename T>
bool TreeSet<T>::containsAll(const std::set<T> &s) {
    for (const auto &elem: s) {
        if (treeSet.find(elem) == treeSet.end()) {
            return false;
        }
    }
    return true;
}

template<typename T>
bool TreeSet<T>::removeAll(const std::set<T> &s) {
    bool changed = false;
    for (const auto &elem: s) {
        changed |= (treeSet.erase(elem) > 0);
    }
    return changed;
}

template<typename T>
bool TreeSet<T>::retainAll(const std::set<T> &s) {
    bool changed = false;
    for (auto it = treeSet.begin(); it != treeSet.end();) {
        if (s.find(*it) == s.end()) {
            it = treeSet.erase(it);
            changed = true;
        } else {
            ++it;
        }
    }
    return changed;
}

/*迭代器*/
template<typename T>
TreeSetIterator<T> TreeSet<T>::iterator() {
    return TreeSetIterator<T>(treeSet);
}

template<typename T>
TreeSetIterator<T> TreeSet<T>::descendingIterator() {
    return TreeSetIterator<T>(treeSet);
}

/*范围视图*/
template<typename T>
std::set<T> TreeSet<T>::descendingSet() {
    std::set<T> descending;
    for (auto it = treeSet.rbegin(); it != treeSet.rend(); ++it) {
        descending.insert(*it);
    }
    return descending;
}

template<typename T>
std::set<T> TreeSet<T>::subSet(T fromElement, bool fromInclusive, T toElement, bool toInclusive) {
    std::set<T> subset;
    auto itFrom = treeSet.lower_bound(fromElement);
    auto itTo = treeSet.upper_bound(toElement);
    if (!fromInclusive) {
        itFrom = treeSet.upper_bound(fromElement);
    }
    if (!toInclusive) {
        itTo = treeSet.lower_bound(toElement);
    }
    for (auto it = itFrom; it != itTo; ++it) {
        subset.insert(*it);
    }
    return subset;
}

template<typename T>
std::set<T> TreeSet<T>::headSet(T toElement, bool inclusive) {
    return subSet(*treeSet.begin(), true, toElement, inclusive);
}

template<typename T>
std::set<T> TreeSet<T>::tailSet(T fromElement, bool inclusive) {
    return subSet(fromElement, inclusive, *treeSet.rbegin(), true);
}

template<typename T>
std::set<T> TreeSet<T>::subSet(T fromElement, T toElement) {
    return subSet(fromElement, true, toElement, false);
}

template<typename T>
std::set<T> TreeSet<T>::headSet(T toElement) {
    return headSet(toElement, false);
}

template<typename T>
std::set<T> TreeSet<T>::tailSet(T fromElement) {
    return tailSet(fromElement, false);
}

/*数组操作，C++中的数组就是std::vector*/
template<typename T>
std::vector<T> TreeSet<T>::toArray() {
    std::vector<T> result;
    for (const auto &elem: treeSet) {
        result.push_back(elem);
    }
    return result;
}

template<typename T>
template<typename U>
std::vector<U> TreeSet<T>::toArray(std::vector<U> &a) {
    a.clear();
    for (const auto &elem: treeSet) {
        a.push_back(static_cast<U>(elem));
    }
    return a;
}

/*比较和哈希*/
template<typename T>
TreeSetComparator<T> TreeSet<T>::getComparator() {
    return comparator;
}

template<typename T>
typename std::set<T>::key_compare TreeSet<T>::getKeyComparator() {
    return treeSet.key_comp();
}

template<typename T>
std::set<T> TreeSet<T>::spliterator() {
    return treeSet;
}

int TreeSet_main() {
    TreeSet<int> *treeSet = new TreeSet<int>(TreeSetComparator<int>());
    TreeSet<int> *treeSet2 = new TreeSet<int>(std::set<int>());
    std::set<int> set;
    for (int i = 0; i < 8; ++i) {
        treeSet->add(i);
        treeSet2->add(i);
        set.insert(i * 2);
    }
    treeSet->addAll(set);
    treeSet->remove(3);
    treeSet->size();
    TreeSetIterator<int> it = treeSet->iterator();
    while (it.hasNext()) {
        int next = it.next();
        std::cout << "TreeSet_main: next=" << next << std::endl;
        it.remove();
    }
    const std::vector<int> &v = treeSet->toArray();
    for (auto itr = v.begin(); itr != v.end(); itr++) {
        std::cout << "TreeSet_main: it=" << itr.base() << std::endl;
    }
    treeSet->removeAll(set);
    treeSet->clear();
    delete treeSet;
    delete treeSet2;
    return 0;
}